/*
 * @lc app=leetcode.cn id=69 lang=javascript
 *
 * [69] x 的平方根
 */

// @lc code=start
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  // 特殊值判断
  if (x == 0) {
    return 0;
  }
  if (x == 1) {
    return 1;
  }
  let left = 1;
  let right = x;
  // 在区间 [left..right] 查找目标元素
  while (left < right) {
    let mid = left + (right - left) / 2;
    if (mid * mid <= x) {
      // 下一轮搜索区间是 [left..mid - 1]
      right = mid - 1;
    } else {
      // 下一轮搜索区间是 [mid..right]
      left = mid;
    }
  }
  return left;
};
// @lc code=end
